Minimum Spanning Tree (MST) of a random generated connected Graph¶

1. Random connected undirected Graph Generation and visualization¶

In [1]:
"""
This is Matteo M.'s final Project for Stanford's Code in Place 2024. 
This program find the Minimum Spanning Tree in an undirected,connected, weighted graph.
It will the visualize the path in multiple visualization tool utilizing gravis library 
and jupyter notebook.

For the sake of the presentation, the graph is randomly generated utilizing Erdős–Rényi model
and enforcing the connection. The code can be easily corrected to accept a graph from user files.

"""
import gravis as gv
import networkx as nx
import random
from itertools import combinations, groupby

# Create a graph of N nodes, with a probability of P of being connected
N = 15
P = 0.2
edges = combinations(range(N), 2)
G = nx.Graph()
G.add_nodes_from(range(N))

for _, node_edges in groupby(edges, key=lambda x: x[0]):
    node_edges = list(node_edges)
    random_edge = random.choice(node_edges)
    G.add_edge(*random_edge)
    for e in node_edges:
        if random.random() < P:
            G.add_edge(*e)
            
# Generate random weight parameter for the edges            
for (start, end) in G.edges:
    G.edges[start, end]['weight'] = random.randint(1,100)
    
#Assign graph and edges
graph_input = G    
graph_input.edges.data('weight')


# Centrality calculation
centrality = nx.algorithms.degree_centrality(graph_input)

# Community detection
communities = nx.algorithms.community.greedy_modularity_communities(graph_input)

# Assignment of node sizes
nx.set_node_attributes(graph_input, centrality, 'size')

for node in graph_input.nodes:
    graph_input.nodes[node]['color'] = 'Red'
    graph_input.nodes[node]['size'] = 10
    

# Plot the graph    
gv.three(graph_input, use_edge_size_normalization=True, edge_size_factor = 4.0) 
Out[1]:
Details for selected element
General
App state
Display mode
Export
Data selection
Graph
Node label text
Node size
Minimum
Maximum
Edge size
Minimum
Maximum
Nodes
Visibility
Size
Scaling factor
Position
Drag behavior
Hover behavior
Node images
Visibility
Size
Scaling factor
Node labels
Visibility
Size
Scaling factor
Edges
Visibility
Size
Scaling factor
Form
Curvature
Hover behavior
Layout algorithm
Simulation
Many-body force
Strength
Theta
Min
Max
Links force
Distance
Strength
x-positioning force
Strength
y-positioning force
Strength
z-positioning force
Strength
Centering force

2. Minimum Spanning Tree determination with Prim's Algorithm¶

In [2]:
# Find the minimum spanning tree
mst = nx.minimum_spanning_tree(G,algorithm="prim")

# Color the edge path in green 
for e in mst.edges:
    mst.edges[e]['color'] = 'green'

# Plot the Minimun Spanning Tree finded
gv.three(mst, use_edge_size_normalization=True, edge_size_factor = 4.0)
Out[2]:
Details for selected element
General
App state
Display mode
Export
Data selection
Graph
Node label text
Node size
Minimum
Maximum
Edge size
Minimum
Maximum
Nodes
Visibility
Size
Scaling factor
Position
Drag behavior
Hover behavior
Node images
Visibility
Size
Scaling factor
Node labels
Visibility
Size
Scaling factor
Edges
Visibility
Size
Scaling factor
Form
Curvature
Hover behavior
Layout algorithm
Simulation
Many-body force
Strength
Theta
Min
Max
Links force
Distance
Strength
x-positioning force
Strength
y-positioning force
Strength
z-positioning force
Strength
Centering force

3. Plot of the MST over the original Graph¶

In [3]:
# Add the Minimum Spanning tree path in the original graph, the mst line will show ticker and colored green
for e in mst.edges:
    graph_input.edges[e]['color'] = 'green'
    graph_input.edges[e]['size'] = 1.2
    
# Plot the graph with the minimum spanning tree
gv.three(graph_input, use_edge_size_normalization = True,edge_size_factor = 0.4)
Out[3]:
Details for selected element
General
App state
Display mode
Export
Data selection
Graph
Node label text
Node size
Minimum
Maximum
Edge size
Minimum
Maximum
Nodes
Visibility
Size
Scaling factor
Position
Drag behavior
Hover behavior
Node images
Visibility
Size
Scaling factor
Node labels
Visibility
Size
Scaling factor
Edges
Visibility
Size
Scaling factor
Form
Curvature
Hover behavior
Layout algorithm
Simulation
Many-body force
Strength
Theta
Min
Max
Links force
Distance
Strength
x-positioning force
Strength
y-positioning force
Strength
z-positioning force
Strength
Centering force

4. Bi-dimensional rappresentation of the Graph¶

In [4]:
# Add a  bi-dimensional model of the graph with the mst path highlighted
gv.vis(graph_input, show_node_label = True, show_edge_label = True, 
       edge_label_data_source = 'weight',node_label_size_factor = 1.5)
Out[4]:
Details for selected element
General
App state
Display mode
Export
Data selection
Graph
Node label text
Edge label text
Node size
Minimum
Maximum
Edge size
Minimum
Maximum
Nodes
Visibility
Size
Scaling factor
Position
Drag behavior
Hover behavior
Node images
Visibility
Size
Scaling factor
Node labels
Visibility
Size
Scaling factor
Rotation
Angle
Edges
Visibility
Size
Scaling factor
Form
Curvature
Hover behavior
Edge labels
Visibility
Size
Scaling factor
Rotation
Angle
Layout algorithm
Simulation
Algorithm
Parameters
Gravitational constant
Spring length
Spring constant
Avoid overlap
Central gravity
In [ ]: